/*
 * Copyright (c) 2007, 2015, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
/*
 * Copyright 1999-2002,2004,2005 The Apache Software Foundation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.sun.org.apache.xerces.internal.dom;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.List;
import java.util.Vector;

import org.w3c.dom.DOMException;
import org.w3c.dom.NamedNodeMap;
import org.w3c.dom.Node;

/**
 * NamedNodeMaps represent collections of Nodes that can be accessed
 * by name. Entity and Notation nodes are stored in NamedNodeMaps
 * attached to the DocumentType. Attributes are placed in a NamedNodeMap
 * attached to the elem they're related too. However, because attributes
 * require more work, such as firing mutation events, they are stored in
 * a subclass of NamedNodeMapImpl.
 * <P>
 * Only one Node may be stored per name; attempting to
 * store another will replace the previous value.
 * <P>
 * NOTE: The "primary" storage key is taken from the NodeName attribute of the
 * node. The "secondary" storage key is the namespaceURI and localName, when
 * accessed by DOM level 2 nodes. All nodes, even DOM Level 2 nodes are stored
 * in a single Vector sorted by the primary "nodename" key.
 * <P>
 * NOTE: item()'s integer index does _not_ imply that the named nodes
 * must be stored in an array; that's only an access method. Note too
 * that these indices are "live"; if someone changes the map's
 * contents, the indices associated with nodes may change.
 * <P>
 *
 * @version $Id: NamedNodeMapImpl.java,v 1.8 2010-11-01 04:39:39 joehw Exp $
 * @xerces.internal
 * @since PR-DOM-Level-1-19980818.
 */
public class NamedNodeMapImpl
    implements NamedNodeMap, Serializable {

  //
  // Constants
  //

  /**
   * Serialization version.
   */
  static final long serialVersionUID = -7039242451046758020L;

  //
  // Data
  //

  protected short flags;

  protected final static short READONLY = 0x1 << 0;
  protected final static short CHANGED = 0x1 << 1;
  protected final static short HASDEFAULTS = 0x1 << 2;

  /**
   * Nodes.
   */
  protected List nodes;

  protected NodeImpl ownerNode; // the node this map belongs to

  //
  // Constructors
  //

  /**
   * Constructs a named node map.
   */
  protected NamedNodeMapImpl(NodeImpl ownerNode) {
    this.ownerNode = ownerNode;
  }

  //
  // NamedNodeMap methods
  //

  /**
   * Report how many nodes are currently stored in this NamedNodeMap.
   * Caveat: This is a count rather than an index, so the
   * highest-numbered node at any time can be accessed via
   * item(getLength()-1).
   */
  public int getLength() {
    return (nodes != null) ? nodes.size() : 0;
  }

  /**
   * Retrieve an item from the map by 0-based index.
   *
   * @param index Which item to retrieve. Note that indices are just an enumeration of the current
   * contents; they aren't guaranteed to be stable, nor do they imply any promises about the order
   * of the NamedNodeMap's contents. In other words, DO NOT assume either that index(i) will always
   * refer to the same entry, or that there is any stable ordering of entries... and be prepared for
   * double-reporting or skips as insertion and deletion occur.
   * @return the node which currenly has the specified index, or null if index is greater than or
   * equal to getLength().
   */
  public Node item(int index) {
    return (nodes != null && index < nodes.size()) ?
        (Node) (nodes.get(index)) : null;
  }

  /**
   * Retrieve a node by name.
   *
   * @param name Name of a node to look up.
   * @return the Node (of unspecified sub-class) stored with that name, or null if no value has been
   * assigned to that name.
   */
  public Node getNamedItem(String name) {

    int i = findNamePoint(name, 0);
    return (i < 0) ? null : (Node) (nodes.get(i));

  } // getNamedItem(String):Node

  /**
   * Introduced in DOM Level 2. <p>
   * Retrieves a node specified by local name and namespace URI.
   *
   * @param namespaceURI The namespace URI of the node to retrieve. When it is null or an empty
   * string, this method behaves like getNamedItem.
   * @param localName The local name of the node to retrieve.
   * @return Node         A Node (of any type) with the specified name, or null if the specified
   * name did not identify any node in the map.
   */
  public Node getNamedItemNS(String namespaceURI, String localName) {

    int i = findNamePoint(namespaceURI, localName);
    return (i < 0) ? null : (Node) (nodes.get(i));

  } // getNamedItemNS(String,String):Node

  /**
   * Adds a node using its nodeName attribute.
   * As the nodeName attribute is used to derive the name which the node must be
   * stored under, multiple nodes of certain types (those that have a "special" string
   * value) cannot be stored as the names would clash. This is seen as preferable to
   * allowing nodes to be aliased.
   *
   * @param arg A node to store in a named node map. The node will later be accessible using the
   * value of the namespaceURI and localName attribute of the node. If a node with those namespace
   * URI and local name is already present in the map, it is replaced by the new one.
   * @return If the new Node replaces an existing node the replaced Node is returned, otherwise null
   * is returned.
   * @throws org.w3c.dom.DOMException The exception description.
   * @see org.w3c.dom.NamedNodeMap#setNamedItem
   */
  public Node setNamedItem(Node arg)
      throws DOMException {

    CoreDocumentImpl ownerDocument = ownerNode.ownerDocument();
    if (ownerDocument.errorChecking) {
      if (isReadOnly()) {
        String msg = DOMMessageFormatter
            .formatMessage(DOMMessageFormatter.DOM_DOMAIN, "NO_MODIFICATION_ALLOWED_ERR", null);
        throw new DOMException(DOMException.NO_MODIFICATION_ALLOWED_ERR, msg);
      }
      if (arg.getOwnerDocument() != ownerDocument) {
        String msg = DOMMessageFormatter
            .formatMessage(DOMMessageFormatter.DOM_DOMAIN, "WRONG_DOCUMENT_ERR", null);
        throw new DOMException(DOMException.WRONG_DOCUMENT_ERR, msg);
      }
    }

    int i = findNamePoint(arg.getNodeName(), 0);
    NodeImpl previous = null;
    if (i >= 0) {
      previous = (NodeImpl) nodes.get(i);
      nodes.set(i, arg);
    } else {
      i = -1 - i; // Insert point (may be end of list)
      if (null == nodes) {
        nodes = new ArrayList(5);
      }
      nodes.add(i, arg);
    }
    return previous;

  } // setNamedItem(Node):Node

  /**
   * Adds a node using its namespaceURI and localName.
   *
   * @param arg A node to store in a named node map. The node will later be accessible using the
   * value of the namespaceURI and localName attribute of the node. If a node with those namespace
   * URI and local name is already present in the map, it is replaced by the new one.
   * @return If the new Node replaces an existing node the replaced Node is returned, otherwise null
   * is returned.
   * @see org.w3c.dom.NamedNodeMap#setNamedItem
   */
  public Node setNamedItemNS(Node arg)
      throws DOMException {

    CoreDocumentImpl ownerDocument = ownerNode.ownerDocument();
    if (ownerDocument.errorChecking) {
      if (isReadOnly()) {
        String msg = DOMMessageFormatter
            .formatMessage(DOMMessageFormatter.DOM_DOMAIN, "NO_MODIFICATION_ALLOWED_ERR", null);
        throw new DOMException(DOMException.NO_MODIFICATION_ALLOWED_ERR, msg);
      }

      if (arg.getOwnerDocument() != ownerDocument) {
        String msg = DOMMessageFormatter
            .formatMessage(DOMMessageFormatter.DOM_DOMAIN, "WRONG_DOCUMENT_ERR", null);
        throw new DOMException(DOMException.WRONG_DOCUMENT_ERR, msg);
      }
    }

    int i = findNamePoint(arg.getNamespaceURI(), arg.getLocalName());
    NodeImpl previous = null;
    if (i >= 0) {
      previous = (NodeImpl) nodes.get(i);
      nodes.set(i, arg);
    } else {
      // If we can't find by namespaceURI, localName, then we find by
      // nodeName so we know where to insert.
      i = findNamePoint(arg.getNodeName(), 0);
      if (i >= 0) {
        previous = (NodeImpl) nodes.get(i);
        nodes.add(i, arg);
      } else {
        i = -1 - i; // Insert point (may be end of list)
        if (null == nodes) {
          nodes = new ArrayList(5);
        }
        nodes.add(i, arg);
      }
    }
    return previous;

  } // setNamedItemNS(Node):Node

  /**
   * Removes a node specified by name.
   * @param name The name of a node to remove.
   * @return The node removed from the map if a node with such a name exists.
   */
  /***/
  public Node removeNamedItem(String name)
      throws DOMException {

    if (isReadOnly()) {
      String msg = DOMMessageFormatter
          .formatMessage(DOMMessageFormatter.DOM_DOMAIN, "NO_MODIFICATION_ALLOWED_ERR", null);
      throw
          new DOMException(DOMException.NO_MODIFICATION_ALLOWED_ERR,
              msg);
    }
    int i = findNamePoint(name, 0);
    if (i < 0) {
      String msg = DOMMessageFormatter
          .formatMessage(DOMMessageFormatter.DOM_DOMAIN, "NOT_FOUND_ERR", null);
      throw new DOMException(DOMException.NOT_FOUND_ERR, msg);
    }

    NodeImpl n = (NodeImpl) nodes.get(i);
    nodes.remove(i);

    return n;

  } // removeNamedItem(String):Node

  /**
   * Introduced in DOM Level 2. <p>
   * Removes a node specified by local name and namespace URI.
   *
   * @param namespaceURI The namespace URI of the node to remove. When it is null or an empty
   * string, this method behaves like removeNamedItem.
   * @param name The local name of the node to remove.
   * @return Node         The node removed from the map if a node with such a local name and
   * namespace URI exists.
   * @throws NOT_FOUND_ERR: Raised if there is no node named name in the map.
   */
  public Node removeNamedItemNS(String namespaceURI, String name)
      throws DOMException {

    if (isReadOnly()) {
      String msg = DOMMessageFormatter
          .formatMessage(DOMMessageFormatter.DOM_DOMAIN, "NO_MODIFICATION_ALLOWED_ERR", null);
      throw
          new DOMException(DOMException.NO_MODIFICATION_ALLOWED_ERR,
              msg);
    }
    int i = findNamePoint(namespaceURI, name);
    if (i < 0) {
      String msg = DOMMessageFormatter
          .formatMessage(DOMMessageFormatter.DOM_DOMAIN, "NOT_FOUND_ERR", null);
      throw new DOMException(DOMException.NOT_FOUND_ERR, msg);
    }

    NodeImpl n = (NodeImpl) nodes.get(i);
    nodes.remove(i);

    return n;

  } // removeNamedItem(String):Node

  //
  // Public methods
  //

  /**
   * Cloning a NamedNodeMap is a DEEP OPERATION; it always clones
   * all the nodes contained in the map.
   */

  public NamedNodeMapImpl cloneMap(NodeImpl ownerNode) {
    NamedNodeMapImpl newmap = new NamedNodeMapImpl(ownerNode);
    newmap.cloneContent(this);
    return newmap;
  }

  protected void cloneContent(NamedNodeMapImpl srcmap) {
    List srcnodes = srcmap.nodes;
    if (srcnodes != null) {
      int size = srcnodes.size();
      if (size != 0) {
        if (nodes == null) {
          nodes = new ArrayList(size);
        } else {
          nodes.clear();
        }
        for (int i = 0; i < size; ++i) {
          NodeImpl n = (NodeImpl) srcmap.nodes.get(i);
          NodeImpl clone = (NodeImpl) n.cloneNode(true);
          clone.isSpecified(n.isSpecified());
          nodes.add(clone);
        }
      }
    }
  } // cloneMap():NamedNodeMapImpl

  //
  // Package methods
  //

  /**
   * Internal subroutine to allow read-only Nodes to make their contained
   * NamedNodeMaps readonly too. I expect that in fact the shallow
   * version of this operation will never be
   *
   * @param readOnly boolean true to make read-only, false to permit editing.
   * @param deep boolean true to pass this request along to the contained nodes, false to only
   * toggle the NamedNodeMap itself. I expect that the shallow version of this operation will never
   * be used, but I want to design it in now, while I'm thinking about it.
   */
  void setReadOnly(boolean readOnly, boolean deep) {
    isReadOnly(readOnly);
    if (deep && nodes != null) {
      for (int i = nodes.size() - 1; i >= 0; i--) {
        ((NodeImpl) nodes.get(i)).setReadOnly(readOnly, deep);
      }
    }
  } // setReadOnly(boolean,boolean)

  /**
   * Internal subroutine returns this NodeNameMap's (shallow) readOnly value.
   */
  boolean getReadOnly() {
    return isReadOnly();
  } // getReadOnly()

  //
  // Protected methods
  //

  /**
   * NON-DOM
   * set the ownerDocument of this node, and the attributes it contains
   */
  protected void setOwnerDocument(CoreDocumentImpl doc) {
    if (nodes != null) {
      final int size = nodes.size();
      for (int i = 0; i < size; ++i) {
        ((NodeImpl) item(i)).setOwnerDocument(doc);
      }
    }
  }

  final boolean isReadOnly() {
    return (flags & READONLY) != 0;
  }

  final void isReadOnly(boolean value) {
    flags = (short) (value ? flags | READONLY : flags & ~READONLY);
  }

  final boolean changed() {
    return (flags & CHANGED) != 0;
  }

  final void changed(boolean value) {
    flags = (short) (value ? flags | CHANGED : flags & ~CHANGED);
  }

  final boolean hasDefaults() {
    return (flags & HASDEFAULTS) != 0;
  }

  final void hasDefaults(boolean value) {
    flags = (short) (value ? flags | HASDEFAULTS : flags & ~HASDEFAULTS);
  }

  //
  // Private methods
  //

  /**
   * Subroutine: Locate the named item, or the point at which said item
   * should be added.
   *
   * @param name Name of a node to look up.
   * @return If positive or zero, the index of the found item. If negative, index of the appropriate
   * point at which to insert the item, encoded as -1-index and hence reconvertable by subtracting
   * it from -1. (Encoding because I don't want to recompare the strings but don't want to burn
   * bytes on a datatype to hold a flagged value.)
   */
  protected int findNamePoint(String name, int start) {

    // Binary search
    int i = 0;
    if (nodes != null) {
      int first = start;
      int last = nodes.size() - 1;

      while (first <= last) {
        i = (first + last) / 2;
        int test = name.compareTo(((Node) (nodes.get(i))).getNodeName());
        if (test == 0) {
          return i; // Name found
        } else if (test < 0) {
          last = i - 1;
        } else {
          first = i + 1;
        }
      }

      if (first > i) {
        i = first;
      }
    }

    return -1 - i; // not-found has to be encoded.

  } // findNamePoint(String):int


  /**
   * This findNamePoint is for DOM Level 2 Namespaces.
   */
  protected int findNamePoint(String namespaceURI, String name) {

    if (nodes == null) {
      return -1;
    }
    if (name == null) {
      return -1;
    }

    // This is a linear search through the same nodes ArrayList.
    // The ArrayList is sorted on the DOM Level 1 nodename.
    // The DOM Level 2 NS keys are namespaceURI and Localname,
    // so we must linear search thru it.
    // In addition, to get this to work with nodes without any namespace
    // (namespaceURI and localNames are both null) we then use the nodeName
    // as a secondary key.
    final int size = nodes.size();
    for (int i = 0; i < size; ++i) {
      NodeImpl a = (NodeImpl) nodes.get(i);
      String aNamespaceURI = a.getNamespaceURI();
      String aLocalName = a.getLocalName();
      if (namespaceURI == null) {
        if (aNamespaceURI == null
            &&
            (name.equals(aLocalName)
                ||
                (aLocalName == null && name.equals(a.getNodeName())))) {
          return i;
        }
      } else {
        if (namespaceURI.equals(aNamespaceURI)
            &&
            name.equals(aLocalName)) {
          return i;
        }
      }
    }
    return -1;
  }

  // compare 2 nodes in the map.  If a precedes b, return true, otherwise
  // return false
  protected boolean precedes(Node a, Node b) {

    if (nodes != null) {
      final int size = nodes.size();
      for (int i = 0; i < size; ++i) {
        Node n = (Node) nodes.get(i);
        if (n == a) {
          return true;
        }
        if (n == b) {
          return false;
        }
      }
    }
    return false;
  }


  /**
   * NON-DOM: Remove attribute at specified index
   */
  protected void removeItem(int index) {
    if (nodes != null && index < nodes.size()) {
      nodes.remove(index);
    }
  }


  protected Object getItem(int index) {
    if (nodes != null) {
      return nodes.get(index);
    }
    return null;
  }

  protected int addItem(Node arg) {
    int i = findNamePoint(arg.getNamespaceURI(), arg.getLocalName());
    if (i >= 0) {
      nodes.set(i, arg);
    } else {
      // If we can't find by namespaceURI, localName, then we find by
      // nodeName so we know where to insert.
      i = findNamePoint(arg.getNodeName(), 0);
      if (i >= 0) {
        nodes.add(i, arg);
      } else {
        i = -1 - i; // Insert point (may be end of list)
        if (null == nodes) {
          nodes = new ArrayList(5);
        }
        nodes.add(i, arg);
      }
    }
    return i;
  }

  /**
   * NON-DOM: copy content of this map into the specified ArrayList
   *
   * @param list ArrayList to copy information into.
   * @return A copy of this node named map
   */
  protected ArrayList cloneMap(ArrayList list) {
    if (list == null) {
      list = new ArrayList(5);
    }
    list.clear();
    if (nodes != null) {
      final int size = nodes.size();
      for (int i = 0; i < size; ++i) {
        list.add(nodes.get(i));
      }
    }
    return list;
  }

  protected int getNamedItemIndex(String namespaceURI, String localName) {
    return findNamePoint(namespaceURI, localName);
  }

  /**
   * NON-DOM remove all elements from this map
   */
  public void removeAll() {
    if (nodes != null) {
      nodes.clear();
    }
  }

  private void readObject(ObjectInputStream in)
      throws IOException, ClassNotFoundException {
    in.defaultReadObject();
    if (nodes != null) {
      nodes = new ArrayList(nodes);
    }
  }

  private void writeObject(ObjectOutputStream out) throws IOException {
    List oldNodes = this.nodes;
    try {
      if (oldNodes != null) {
        this.nodes = new Vector(oldNodes);
      }
      out.defaultWriteObject();
    }
    // If the write fails for some reason ensure
    // that we restore the original object.
    finally {
      this.nodes = oldNodes;
    }
  }

} // class NamedNodeMapImpl
